Steady advances in miniaturization techniques for integrated circuits have resulted in circuit devices, particularly transistors, of ever-diminishing sizes. Generally speaking, each generation of an integrated circuit utilizes transistors that occupy smaller footprints on the semiconductor substrate than those of the previous generation. However, consumer desires, with resultant design demands, seem to grow even faster than integrated circuit devices have been shrinking. As a result, rather than being in surplus, substrate real estate remains at a premium. Every unit area of a substrate must be maximally utilized to squeeze as much performance as possible into the limited space of the circuit die. If a way can be found to reduce the size of a circuit in one portion of a chip, the area thereby freed up can be used to support additional circuitry to pack even more logic functionality into the same die. The miniaturization race therefore involves not only reducing the footprint of individual devices, such as transistors, on the die, but also finding ways to use fewer such devices to achieve the same functionality.
Many digital designs employ read-only memory (ROM), which is built directly onto the same die with the rest of the circuit. This on-chip ROM provides necessary data for the circuit, such as microcode instructions, object code, operating parameters and the like. Generally, read-only memory (ROM) has N address lines as input for accessing 2N data words respectively stored within the ROM at 2N addresses, where N≧2. Each data word may hold M data bits, M≧1, which are provided on M respective bit output lines. Hence, at a high level of abstraction, a ROM stores a data set and implements a 2N×M look-up table with this data set, in which the input value is provided on the N address lines, and the output result is provided on the M bit output lines. By way of example, the following 23×3 data set is considered:
TABLE 1AddressData word(A2, A1, A0)B0B1B20 (0, 0, 0)0011 (0, 0, 1)0102 (0, 1, 0)0013 (0, 1, 1)1104 (1, 0, 0)1105 (1, 0, 1)0016 (1, 1, 0)0117 (1, 1, 1)010
Three address input bits, A0, A1 and A2, provide eight addresses, 0 to 7, each of which stores a data word of three bits, B0, B1 and B2. Although specific reference in the following is drawn to an 8×3 data set, the principles are applicable to any generalized 2N×M data set, as is known in the art, where N is the number of address bits, and M is the number of bits in the data word.
A prior art design for a ROM 10 that implements the data set of Table 1 is shown in FIG. 1A. The prior art design 10 comprises three bit output lines B0, B1 and B2, and eight address decode lines D0 to D7 connected to an address decoder 12. The address decode lines D0-D7 are normally low. The decoder 12 is an N to 2N decoder. In the specific example, the decoder 12 accepts as input three address lines A0, A1 and A2, and based upon this input selects, or asserts, one of the 23 address decode lines D0-D7. Since the ROM 10 uses true logic, when an address decode line D0-D7 is asserted, that address decode line D0-D7 goes high. The decoder 12 creates a one-to-one correspondence between input values provided by address lines A0-A2 and selected address decode lines D0-D7, wherein when an address “x” is placed upon address lines A0-A2, the decoder 12 asserts, or raises, address decode line Dx. For example, if the address inputs (A2, A1, A0) are (0, 0, 0), then the decoder 12 will assert address decode line D0; all other address decode lines D1-D7 are not asserted, and so remain low. Similarly, if the address inputs (A2, A1, A0) are (1, 1, 1), then the decoder 12 will assert address decode line D7, and all other address decode lines D0-D6 are not asserted. In the following, it is assumed that A2 is the high order address bit, and that A0 is the low order address bit.
Each bit output line B0-B2 is tied to ground via a pull-down resistor 14, and is therefore normally in a logical zero state. By utilizing any suitable connecting device 16 to selectively electrically connect each bit output line B0-B2 to zero or more address decode lines D0-D7, it is possible to implement the data set of Table 1. By electrically connecting a bit output line B0-B2 to an address decode line D0-D7, the normally-low bit output line B0-B2 will go high when the address decode line D0-D7 is asserted. Each connecting device 16 may therefore represent a logical one for the corresponding output bit B0-B2 at a corresponding value of the input address provided by address lines A0-A2.
For the sake of simplicity, the connecting device 16 of FIG. 1A is shown as a diode 16. One of skill in the art will readily recognize that this diode 16 may, in fact, be implemented by a transistor. Hence, one way to implement the logic array 18 is by using MOS transistors 16 for the connecting devices, rather than diodes. It should be noted that when diodes are used as connecting devices, a diode is typically electrically connected when the associated bit is supposed to be ‘1’, whereas if a MOS transistor is used as the connecting device then the transistor is typically connected for all those bits where the output is supposed to be ‘0’. But for this difference, the remainder of the logic and following discussion hold for both diode and transistor based configurations.
By way of an example that utilizes a transistor-based configuration, reference is further drawn to FIG. 1B. The top three transistors 11 in FIG. 1B act as pre-charge transistors 11. Before reading from a location in the ROM 10, all the bit output lines B0, B1, B2 are pre-charged using the pre-charge logic 17. Depending on the decoder 12 output, the specific output bit lines B0, B1, B2 will be discharged. Of course, any suitable component known in the art may be used for the connecting devices 16.
For example, as shown in FIGS. 1A and 1B, when the input address (A2, A1, A0) is (0, 0, 0), the output data word (B0, B1, B2) provided by bit output lines B0-B2 is (0, 0, 1). In FIG. 1A, bit output line B2 is electrically connected to address decode line D0 with a connecting device 16, while bit output lines B0 and B1 are not connected to address decode line D0; the reverse is true in FIG. 1B, so as to provide the same logical output. Similarly, based on Table 1, an output data word (B0, B1, B2) of (1, 1, 0) is desired when the input address (A2, A1, A0) is (0, 1, 1) or (1, 0, 0). The address (0, 1, 1) selects address decode line D3; address (1, 0, 0) selects address decode line D4. As a result, bit output lines B0 and B1 are both electrically connected to address decode lines D3 and D4 in FIG. 1A, using four respective connecting devices 16. On the other hand, in FIG. 1B, these bit output lines are not connected, and instead bit output line B2 is connected to address decode lines D3 and D4. The entirety of the data set provided by Table 1 may in this manner be encoded into the initial ROM design 10 with the logic array 18, wherein each address decode line D0-D7 stores, or encodes, the corresponding data word for that address.
One of reasonable skill in the art will readily note that the ROM 10 can also be configured as a 2-D structure, with both column and row decoders. Such a 2-D structure is simply a slightly more complex generalization of the structure shown in FIGS. 1A and 1B, and is known in the art.
Because ROM is such a ubiquitous component, it would be highly beneficial if a method could be found to reduce the footprint of the ROM, and thereby free up substrate real estate for other circuit components. In particular, since the logic array 18 that encodes the data set occupies a relatively large footprint, it would be particularly beneficial if the size of the logic array 18 could be reduced.